package jun;

import java.util.*;
import java.util.function.BiFunction;

/**
 * @author ：冯涛滔
 * @date ：Created in 2020-6-3 9:26
 * @description：
 * @modified By：
 * @version:
 */
public class Jun03 {
    /**
     * create by: 冯涛滔
     * description: https://leetcode-cn.com/problems/minimum-add-to-make-parentheses-valid/ 使括号有效的最少添加
     * create time: 2020-6-3 9:28
     * @eturn a
     * @params
     */
    public int minAddToMakeValid(String S) {
        char[] list = S.toCharArray();
        int left = 0; //(的需求量
        int right = 0; //)的需求量
        for (int i = 0; i < list.length; i++) {
            if(list[i]=='('){
                right++;
            }else{
                if(right>0){
                    right--;
                }else {
                    left++;
                }
            }
        }
        return right+left;
    }
    /**
     * create by: 冯涛滔
     * description: https://leetcode-cn.com/problems/non-overlapping-intervals/  435. 无重叠区间
     * 按终点进行排序
     * 会出现两种情况
     * 第一种:  不重叠
     * 第二种: 重叠了 删除当前区间
     * create time: 2020-6-3 9:31
     * @params [intervals]
     * @return int
     */
    public int eraseOverlapIntervals(int[][] intervals) {
        if(intervals. length==0){
            return 0;
        }
        BiFunction<int[],int[],Integer> biFunction = (o1,o2)->o1[0]-o2[0];
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1]-o2[1];
            }
        });
        int res = 1;
        int end = intervals[0][1];//初始化
        for (int i = 1; i < intervals.length; i++) {
           if(intervals[i][0]>=end){ //开始的位置要比上一个位置要大的话 就不重叠
               res++;
               end = intervals[i][1];
           }
        }
        return intervals.length-res;
    }
    public static boolean lemonadeChange(int[] bills) {
        int wu = 0;
        int shi = 0;
        for (int i = 0; i < bills.length; i++) {
            if (bills[i]==5) {
                wu++;
                continue;
            }
            if(bills[i] == 10){
                shi++;
                wu--;
            }
            if(bills[i]== 20){
                if(shi>0){
                    shi--;
                    wu--;
                }else{
                    wu-=3;
                }
            }
            if(wu<0){
                return false;
            }
        }
        return true;
    }
    /**
     * create by: 冯涛滔
     * description: https://leetcode-cn.com/problems/group-the-people-given-the-group-size-they-belong-to/ 1282. 用户分组
     * create time: 2020-6-3 18:18
     * @params [groupSizes]
     * @return java.util.List<java.util.List < java.lang.Integer>>
     */
    public List<List<Integer>> groupThePeople(int[] groupSizes) {
        int N = groupSizes.length;

        List<List<Integer>> ans = new ArrayList<>();
        // 辅助字典： 用户组大小 -> 未满用户组
        Map<Integer,List<Integer>> helper = new HashMap<>();
        for (int i = 0; i < N; i++) {
            // 用户组大小为1
            if(groupSizes[i]==1) {
                ans.add(Arrays.asList(i));
                continue;
            }

            // 用户组
            List<Integer> group =
                    helper.getOrDefault(groupSizes[i], new ArrayList<>());
            // 用户入组
            group.add(i);

            // 用户组新建
            if(group.size()==1) {
                helper.put(groupSizes[i], group);
                ans.add(group);
            }
            // 用户组已满
            else if(group.size()==groupSizes[i]) {
                helper.remove(groupSizes[i]);
            }
        }

        return ans;
    }
    /**
     * create by: 冯涛滔
     * description: https://leetcode-cn.com/problems/boats-to-save-people/ 881. 救生艇
     * create time: 2020-6-3 21:06
     * @params [people, limit]
     * @return int
     */
    public int numRescueBoats(int[] people, int limit) {
        Arrays.sort(people);
        int j = people.length-1;
        int i = 0;
        int res = 0;
        while(i<=j){
            if(people[j]+people[i]<=limit){//每次最重的和
                i++;
            }
            res++;
            j--;

        }
        return res;
    }

    /**
     * create by: 冯涛滔
     * description: https://leetcode-cn.com/problems/last-stone-weight/
     * create time: 2020-6-3 21:41
     *
     * return a
     * @params
     */
    public static int lastStoneWeight(int[] stones) {
        int index = stones.length - 1;
        for(int i = 0; i < stones.length - 1; i++){     //通过stones.length来判断需要操作的次数。（不用将stones.length == 1的情况单独考虑）
            Arrays.sort(stones);//将sort放在循环体的开始。（避免在循环体外再写一次重复的sort（））
            if(stones[index]==0|| stones[index-1] == 0){
                break;
            }
            stones[index] -= stones[index-1];           //两种不同情况使用同一表达式处理。（）
            stones[index-1] = 0;

        }
        return stones[stones.length-1];
    }
    public static void main(String[] args) {
        int[] list = {5,5,5,10,20};
        lastStoneWeight(list);
    }
}
